#include"Heap.h"

//堆的初始化
//void HeapInit(HP* php)
//{
//	php->_a = NULL;
//	php->_capacity = 0;
//    php->_size = 0;
//}
//
//// 堆的销毁
//void HeapDestory(HP* php)
//{
//	assert(php);
//	assert(php->_size > 0);
//
//	free(php->_a);
//	php->_capacity = 0;
//	php->_size = 0;
//}

//向上调整
void AdjustUp(HPDataType* a, int child,int *countB,int *countY)
{

	int parent = (child - 1) / 2;

	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			(*countB)++;
			(*countY)++;
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}

//向下调整
void AdjustDown(HPDataType* a, int n,int parent,int *countB,int *countY)
{
	int child = parent * 2 + 1;


	
	if (a[child+1] < a[child])
	{
		child++;
		(*countB)++;
	}

	while (child < n && a[parent] > a[child])
	{
		(*countB)++;
		(*countY)++;
		Swap(&a[parent], &a[child]);
		parent = child;
		child = parent * 2 + 1;
		if (child+1<n&&a[child + 1] < a[child])
		{
			(*countB)++;
			child++;
		}
	}
}

//// 堆的插入
//void HeapPush(HP* php, HPDataType x)
//{
//	assert(php);
//
//
//	//扩容
//	if (php->_size == php->_capacity)
//	{
//		int newcapacity = php->_capacity == 0 ? 4 : php->_capacity * 2;
//		HPDataType* tmp = (HPDataType*)realloc
//		(php->_a, newcapacity * sizeof(HPDataType));
//		if (tmp == NULL)
//		{
//			perror("realloc fail");
//			return;
//		}
//
//		php->_a = tmp;
//		php->_capacity = newcapacity;
//	}
//
//	php->_a[php->_size++] = x;
//	AdjustUp(php->_a, php->_size - 1);
//
//}
//
//// 堆的删除
//void HeapPop(HP* php)
//{
//	assert(php);
//	assert(php->_size > 0);
//
//	Swap(&php->_a[0], &php->_a[php->_size--]);
//	
//	AdjustDown(php->_a, php->_size, 0);
//
//}
//
//// 取堆顶的数据
//HPDataType HeapTop(HP* php)
//{
//	assert(php);
//	assert(php->_size > 0);
//
//	return php->_a[0];
//}
//
//// 堆的数据个数
//int HeapSize(HP* php)
//{
//	assert(php);
//	assert(php->_size > 0);
//
//	return php->_size - 1;
//}
//
//// 堆的判空                    不空返回1
//int HeapEmpty(HP* php)
//{
//	assert(php);
//	if (php->_size > 0)
//	{
//		return 1;
//	}
//	else
//	{
//		return 0;
//	}
//
//}

void Swap(int* a, int* b)
{
	int c = *a;
	*a = *b;
	*b = c;
}
// 对堆数组进行堆排序  //降序
void HeapSort(HPDataType* a, int n)
{

	//记录比较和移动次数
	int countB = 0;
	int countY = 0;

	//降序, 建小堆
	for (int i = 0; i < n; i++)
	{
		AdjustUp(a, i,&countB,&countY);
	}

	int i = 0;
	int size = n;

	for (size = n; size > 0; size--)
	{
		Swap(&a[size-1], &a[0]);
		countY++;
		AdjustDown(a, size-1,0, &countB, &countY);
	}
	printf("比较次数:%d,移动次数:%d", countB, countY);
}

//TopK问题
//void CreateNDate()
//{
//	// 造数据
//	int n = 10000;
//	srand(time(0));
//	const char* file = "data.txt";
//	FILE* fin = fopen(file, "w");
//	if (fin == NULL)
//	{
//		perror("fopen error");
//		return;
//	}
//
//	for (size_t i = 0; i < n; ++i)
//	{
//		int x = rand() % 1000000;
//		fprintf(fin, "%d\n", x);
//	}
//
//	fclose(fin);
//}

//void PrintTopK(int k)
//{
//	FILE* pf = fopen("data.txt", "r");
//	
//	int a[k];
//	
//	int i = 0;
//	while (i<k)
//	{
//		fscanf(pf, "%d", a[i++]);
//		
//	}
//	//建小堆
//	for ( i = 0; i < k; i++)
//	{
//		AdjustUp(a, i);
//	}
//	int x;
//	while (1)
//	{
//		if (feof(pf))
//		{
//			break;
//		}
//		fscanf(pf, "%d", &x);
//		
//		if (x > a[0])
//		{
//			a[0] = x;
//			AdjustDown(a, k, 0);
//		}
//		
//	}
//}

